package String.easy;

/**
 * 1. 问题描述
 *      给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，
 *      判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。
 *      如果可以构成，返回 true ；否则返回 false。
 *
 *      (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。
 *      杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
 *
 * 2. 算法描述
 *      算法实现1；
 *          首先我们创建一个长度为26的整形数组 arr来记录赎金字符串 arr[key]=value
 *          其中key为当前字符在26个字母中的位置，value为当前字符出现在赎金字符串中的
 *          次数，时间复杂度为O(m),其中m为赎金字符串的长度
 *
 *          第二次我们扫描杂志字符串中的每一个字符，判断当前字符是否出现在赎金字符串中
 *          如果出现我们从arr中对应的位置减1(即减少当前字符的数量)，时间复杂度为O(n)
 *          其中n为杂志字符串的长度
 *
 *          第三次扫描arr，只要arr中有的位置不是0，说明杂志字符串中的字符无法生成赎金
 *          字符串直接返回false，如果arr中的每个位置的值都是0，说明可以生成，返回true
 *          时间复杂度为O(26)
 *
 *          故总的时间复杂度O(m+n+26)，空间复杂度为O(26)
 *          leetcode上显示超过94.96%的用户，空间超过92.41%的用户
 *
 *      算法实现2：计数排序套路框架
 *          我的思路竟然和计数排序的思路相似，但是网上的大佬给的实现只用了两个for循环，我用了
 *          三次for循环，下面看看差异在哪?
 *          首先我们先介绍一下计数排序的定义：
 *               计数排序可以认为是一种特殊的桶排序，为了便于理解，我们引入“桶”这个概念，下面给出计数排序的两个步骤：
 *               1.分配：将初始数据划分为若干个桶，之后把初始数据分配到各自的桶中，其目的是统计每个元素出现的频率；
 *               2.收集：按照需求，从各个桶中依次取出数据，进行排序。
 *
 *           1.对本题来说，因为两个字符串均只含有小写字母，因此我们可以创建一个容量为26的数组，存储magazine字符串中各字母出现的频率；
 *           2.分配：容量为26的数组代表26个桶，每个桶中存储一个小写字母的出现频率，将magazine中各元素分配到相应桶中；
 *           3.收集：遍历ransomNote数组中的元素，查看对应的桶中是否还有该元素，若存在则将其取出，若不存在则返回false。
 *           ps：对于本题来说只有哈希计数，而没有最后的排序，从本质上来说不能归于计数排序，感谢@qing-mo-9的指正！
 *
 *           大佬给的思路是将magazine存入桶内，而我的思路是将ransomNote存放如桶内
 *           然后之间遍历ransomNote
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 赎金信 {
    public static void main(String[] args) {
        System.out.println(canConstruct("ab", "aab"));
    }

    /**
     * 创建一个辅助数组
     * @param ransomNote
     * @param magazine
     * @return
     */
    public static boolean canConstruct(String ransomNote, String magazine) {
        // 判断边界
        if (ransomNote.length() == 0) {return true;}
        // 定义双指针
        int[] arr = new int[26];
        // 扫描ransomNote
        for (int i = 0; i < ransomNote.length(); i++) {
            arr[ransomNote.charAt(i)-'a']++;
        }
        for (int i = 0; i < magazine.length(); i++) {
            char temp = magazine.charAt(i); //
            if (arr[temp-'a'] != 0) {
                arr[temp-'a']--;
            }
        }
        for (int i : arr) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public static boolean canConstruct1(String ransomNote, String magazine) {
        int[] arr = new int[26];
        // 将元素存放如桶内进行计数统计
        for (int i = 0; i < magazine.length(); i++) {
            arr[magazine.charAt(i)-'a']++;
        }
        // 比较
        for (int i = 0; i < ransomNote.length(); i++) {
            if (--arr[ransomNote.charAt(i)-'a'] < 0) {
                return false;
            }
        }
        return true;
    }

    /**
     *
     * 官网上成都电子科大的大佬给的一个思路(真的厉害)，只用了一次遍历
     * 关键之处在于
     * @param ransom
     * @param magazine
     * @return
     */
    public static boolean canConstruct2(String ransom, String magazine) {
        if (magazine.length() < ransom.length()) return false;
        int caps[] = new int[26];
        for (char c : ransom.toCharArray()) {
            int index = magazine.indexOf(c, caps[c - 'a']); // 该方法有几个重构的方法主要含义是查找当前字符在字符串中第一次出先的位置，如果没有返回-1
            if (index == -1)
                return false;
            caps[c - 97] = index + 1;
        }
        return true;
    }
}
